//求最大公约数和最小公倍数方法
#include <math.h>
#include <stdio.h>

#include "../esyio.h"


/*  辗转相除法
 *  32 / 26 = 1...6  (此行除数26作下一行的被除数，余数作为除数)
 *  26 / 6  = 4...2  (此行同理)
 *  6  / 2  = 3...0  (此处余数为零，意味着最大公约数就是2)
 *
 */
void func1(int m, int n) {
    int p, q, r;
    p = m > n ? m : n; //被除数
    q = m + n - p;     //除数
    r = p % q;
    while (r) {
        p = q;
        q = r;
        r = p % q;
    }
    PrintInt(q);
}

//递归实现(默认m>n)
int func2(int m, int n) {
    if (m % n == 0) {
        return n;
    }
    return  func2(n,m%n);
}

int gcd(int m, int n) {
    // 当两个数相等时，它们的值就是它们的最大公约数
    if (m == n) {
        return m;
    }
    // 将两个数中的较大数减去较小数，继续递归调用直到两个数相等
    if (m > n) {
        return gcd(m - n, n);
    } else {
        return gcd(m, n - m);
    }
}






int main() {
    PrintInt(gcd(18,27));

    
    return 0;
}